package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: minFallingPathSum931
 * @description: 给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
 *
 * 下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
 * 输入：[[1,2,3],[4,5,6],[7,8,9]]
 * 输出：12
 * 解释：
 * 可能的下降路径有：
 *
 *     [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
 *     [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
 *     [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
 *
 * 和最小的下降路径是 [1,4,7]，所以答案是 12。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-falling-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/1/2814:21
 * @since V1.0
 */
public class minFallingPathSum931 {

    //动态规划
    //从倒数第二层往上层遍历，通过循环每一层的数字，计算下一层的最小值放到A[r][a] = A[r][a] + min 上。
    public int minFallingPathSum(int[][] A) {
        int N = A.length;
        for (int r = N-2;r>=0;--r){
            for (int a = 0;a<N;a++){
                int min = A[r+1][a];
                //这里可以处理a在边界的情况
                if (a>0){
                    min = Math.min(min,A[r+1][a-1]);
                }
                if(a+1<N){
                    min  = Math.min(min,A[r+1][a+1]);
                }
                A[r][a] +=min;
            }
        }
        int ans = A[0][0];
        for (int x:A[0]){
            ans = Math.min(ans,x);
        }
        return ans;
    }
}
